package 回溯算法;

import java.util.LinkedList;
import java.util.List;

/**
 * @Author: biubiu0002
 * @Date: 2021-03-25 16:42
 **/
public class 组合 {
    List<List<Integer>> res = new LinkedList<>();

    //1...n中 k个数的组合
    public List<List<Integer>> combine(int n, int k) {
        int[] nums = new int[n+1];
        LinkedList<Integer> trace = new LinkedList<>();
        for(int i=1;i<=n;i++){
            nums[i]=i;
        }
        backtrace(nums,1,trace,k);
        return res;



    }

    //basecase:k=trace.size()
    void backtrace(int nums[],int start,LinkedList<Integer> trace,int k){

        if(k==trace.size()){
            res.add(new LinkedList<>(trace));
            return;
        }

        for(int i=start;i<nums.length;i++){
            //排除无效选项
            if(trace.contains(nums[i])){
                continue;
            }
            //做选择
            trace.add(nums[i]);
            //下一层nums的选择下标是i+1...n
            backtrace(nums,i+1,trace,k);
            trace.removeLast();

        }




    }


    public static void main(String[] args) {
        组合 zuhe = new 组合();
        System.out.println(zuhe.combine(4,2));


    }
}
